package algorithm;
import java.util.Random;

/**
 * 二叉树的定义类 二叉树 的插入，查找操作
 *
 * @author lenovo
 */
public class BinaryTree {
    /**根节点**/
    private TreeNode root;

    /***获取根节点*/
    public TreeNode getRoot() {
        return root;
    }

    /**插入操作**/
    public void insertTreeNode(int value) {
        TreeNode newNode = new TreeNode(value);
        if (root == null) {
            /**当根节点为空时，创建根节点**/
            root = newNode;
            root.setLeftTreeNode(null);
            root.setRightTreeNode(null);
        } else {
            TreeNode currentNode = root;
            TreeNode parentNode;
            while (true) {
                parentNode = currentNode;
                /** 往右放**/
                /**System.out.println("parentNode.value ="+parentNode.getValue());**/
                if (newNode.getValue() >= currentNode.getValue()) {
                    /**System.out.println("往右放");**/
                    currentNode = currentNode.getRightTreeNode();
                    if (currentNode == null) {
                        parentNode.setRightTreeNode(newNode);
                        return;
                    }
                } else {
                    /**往左放**/
                    /** System.out.println("往左放");**/
                    currentNode = currentNode.getLeftTreeNode();
                    if (currentNode == null) {
                        parentNode.setLeftTreeNode(newNode);
                        return;
                    }
                }
            }
        }
    }

    /**查找**/
    public TreeNode find(int key) {
        TreeNode currentNode = root;
        if (currentNode != null) {
            while (currentNode.getValue() != key) {
                if (currentNode.getValue() > key) {
                    currentNode = currentNode.getLeftTreeNode();
                } else {
                    currentNode = currentNode.getRightTreeNode();
                }
                if (currentNode == null) {
                    return null;
                }
            }
            if (currentNode.isDeleteFlag()) {
                return null;
            } else {
                return currentNode;
            }
        } else {
            return null;
        }
    }

    /** 二叉树的高度**/
    public int height() {
        return height(root);
    }

    public int height(TreeNode node) {
        /**空树的高度为0**/
        if (node == null) {
            return 0;
        } else {
            /**左右子树的高度**/
            int left_height = height(node.getLeftTreeNode());
            int right_height = height(node.getRightTreeNode());
            /**三目运算 哪边的树高为哪边**/
            return left_height < right_height ? (right_height + 1) : (left_height + 1);
        }
    }

    /**终点的数量**/
    public int size() {
        return size(root);
    }

    public int size(TreeNode node) {
        if (node == null) {
            return 0;
        } else {
            /****/
            return 1 + size(node.getLeftTreeNode()) + size(node.getRightTreeNode());
        }
    }

    /**删除某个节点**/
    public boolean delete(int key) {
        /**查找要删除的节点**/

        TreeNode parentNode = root;
        TreeNode currentNode = root;
        boolean isLeftChild = false;
        while (currentNode.getValue() != key) {
            parentNode = currentNode;
            if (key > currentNode.getValue()) {
                currentNode = currentNode.getRightTreeNode();
                isLeftChild = false;
            } else {
                currentNode = currentNode.getLeftTreeNode();
                isLeftChild = true;
            }
            if (null == currentNode) {
                return false;
            }
        }
        /**被删除的节点没有子节点**/
        if (null == currentNode.getLeftTreeNode() && null == currentNode.getRightTreeNode()) {
            if (currentNode == root) {
                root = null;
            } else {
                if (isLeftChild) {
                    parentNode.leftTreeNode = null;
                } else {
                    parentNode.rightTreeNode = null;
                }
            }
        } else if (null == currentNode.leftTreeNode) {
            /**被删除节点有一个子节点,只有右节点**/
            if (currentNode == root) {
                root = currentNode.rightTreeNode;
            } else if (isLeftChild) {
                parentNode.leftTreeNode = currentNode.rightTreeNode;
            } else {
                parentNode.rightTreeNode = currentNode.rightTreeNode;
            }
        } else if (null == currentNode.rightTreeNode) {
            /**被删除节点有一个子节点,只有左节点**/
            if (currentNode == root) {
                root = currentNode.leftTreeNode;
            } else if (isLeftChild) {
                parentNode.leftTreeNode = currentNode.leftTreeNode;
            } else {
                parentNode.rightTreeNode = currentNode.leftTreeNode;
            }
        } else {

            /** 被删除节点有两个子节点**/
            /** 删除节点的后续节点**/
            TreeNode succeedNode = getSucceedNode(currentNode);
            if (currentNode == root) {
                parentNode.leftTreeNode = succeedNode;
            } else if (isLeftChild) {
                parentNode.leftTreeNode = succeedNode;
            } else {
                parentNode.rightTreeNode = succeedNode;
            }
            succeedNode.leftTreeNode = currentNode.leftTreeNode;

        }
        return true;
    }

    /** 获取节点的后续节点**/
    private TreeNode getSucceedNode(TreeNode delNode) {
        TreeNode parentNode = delNode;
        TreeNode succeedNode = delNode;
        /** 从右节点开始**/
        TreeNode currentNode = delNode.rightTreeNode;

        /** 获取左子节点，一直到最后一个左子节点**/
        while (null != currentNode) {
            parentNode = succeedNode;
            succeedNode = currentNode;
            currentNode = currentNode.leftTreeNode;
        }
        if (succeedNode != delNode.rightTreeNode) {
            parentNode.leftTreeNode = succeedNode.rightTreeNode;
            /** 后续节点要替换到delNode的位置，因此要把后续节点的右节点替换给parent的左节点
            *后续节点的现右子节点就是delNode的右子节点
             **/
            succeedNode.rightTreeNode = delNode.rightTreeNode;
        }
        return succeedNode;

    }


    public void delete_2(int data) {
        /**p指向要删除的节点，初始化指向根节点**/
        TreeNode p = root;
        /** 要删除的节点的父节点**/
        TreeNode parentNode = null;

        while (p != null && p.getValue() != data) {
            /**查找要删除的节点**/
            parentNode = p;
            if (data > p.getValue()) {
                p = p.getRightTreeNode();
            } else {
                p = p.getLeftTreeNode();
            }
        }
        /**没有找到**/
        if (p == null) {
            return;
        }

        /**要删除的节点有两个节点**/
        if (p.leftTreeNode != null && p.rightTreeNode != null) {
            TreeNode minP = p.rightTreeNode;
            /**是minP的父节点**/
            TreeNode minParent = p;

            while (minP.leftTreeNode != null) {
                minParent = minP;
                minP = minP.leftTreeNode;
            }
            /**将minP的值替换到p中**/
            p.value = minP.value;
            /**下面就变成了删除minP**/
            p = minP;
            parentNode = minParent;
        }

        /** 删除节点是叶节点或只有一个子节点**/
        /**p的子节点**/
        TreeNode child;
        if (p.leftTreeNode != null) {
            child = p.leftTreeNode;
        } else if (p.rightTreeNode != null) {
            child = p.rightTreeNode;
        } else {
            child = null;
        }

        if (parentNode == null) {
            /**删除的是根节点**/
            root = child;
        } else if (parentNode.leftTreeNode == p) {
            parentNode.leftTreeNode = child;
        } else {
            parentNode.rightTreeNode = child;
        }
    }

    /**中序遍历 排序 顺序是左根右**/
    public void inOrder(TreeNode treeNode) {
        if (treeNode != null && treeNode.isDeleteFlag() == false) {
            inOrder(treeNode.getLeftTreeNode());
            System.out.print("-->" + treeNode.getValue());
            System.out.print("left-->right");
            inOrder(treeNode.getRightTreeNode());
        }
    }

    /**前序遍历**/
    public void preOrder(TreeNode treeNode) {
        if (treeNode != null && treeNode.isDeleteFlag() == false) {
            preOrder(treeNode.getLeftTreeNode());
            System.out.print("-->" + treeNode.getValue());
            preOrder(treeNode.getRightTreeNode());
        }
    }

    /**后续遍历**/
    public void postOrder(TreeNode treeNode) {
        if (treeNode != null && treeNode.isDeleteFlag() == false) {
            postOrder(treeNode.getRightTreeNode());
            postOrder(treeNode.getLeftTreeNode());
            System.out.print("-->" + treeNode.getValue());
        }
    }

    /**查找最大节点**/
    public static TreeNode findMaxNode(TreeNode treeNode) {
        TreeNode maxNode = treeNode;
        /**二叉树为空时，返回null**/
        if (treeNode == null) {
            return null;
        }
        /**当treeNode只有根节点时，返回根节点**/
        if (treeNode.rightTreeNode == null && treeNode.leftTreeNode == null) {
            return treeNode;
        }
        /**节点有子节点时，先找右节点，后找左节点**/
        if (treeNode.rightTreeNode != null ||
                treeNode.leftTreeNode != null) {
            while (maxNode.rightTreeNode != null && maxNode.leftTreeNode != null) {
                if (maxNode.rightTreeNode != null) {
                    maxNode = maxNode.rightTreeNode;
                } else if (maxNode.rightTreeNode == null && maxNode.leftTreeNode != null) {
                    maxNode = maxNode.leftTreeNode;
                }
            }
        }
        System.out.println(maxNode.value);
        return maxNode;
    }

    /**查找最小节点**/
    public static TreeNode findMinNode(TreeNode treeNode) {
        TreeNode minNode = treeNode;
        /** 二叉树为空时，返回null**/
        if (treeNode == null) {
            return null;
        }
        /**当treeNode只有根节点时，返回根节点**/
        if (treeNode.rightTreeNode == null && treeNode.leftTreeNode == null) {
            return treeNode;
        }
        /**节点有子节点时，找左节点**/
        if (treeNode.leftTreeNode != null) {
            while (minNode.leftTreeNode != null) {
                minNode = minNode.leftTreeNode;
            }
        }
        System.out.println(minNode.value);
        return minNode;
    }

    /**查找前驱节点**/
    public static TreeNode findPreNode(TreeNode rootNode, int data) {

        TreeNode currentNode = rootNode;
        /**父节点**/
        TreeNode preNode = currentNode;
        if (currentNode == null) {
            /**空树*/
            return null;
        } else if (currentNode.leftTreeNode == null && currentNode.rightTreeNode == null) {
            /**只有一个根节点**/
            return null;
        } else {
            /**查找对应值的节点**/
            while (currentNode.value != data) {
                preNode = currentNode;
                if (currentNode.value < data) {
                    currentNode = currentNode.rightTreeNode;
                } else if (currentNode.value > data) {
                    currentNode = currentNode.leftTreeNode;
                }
                if (currentNode == null) {
                    System.out.println("没找到对应值的节点，因此没有前驱节点");
                    return null;
                }
            }
            if (currentNode != null) {
                System.out.println(preNode.value + ":" + currentNode.value);
                return preNode;
            }
        }
        return null;
    }

    /**
     * 二叉树最近公共祖先
     **/
    public  TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.leftTreeNode, p, q);
        TreeNode right = lowestCommonAncestor(root.rightTreeNode, p, q);
        return left == null ? right : right == null ? left : right;
    }

    public BinaryTree insertTreeNodeByInt(BinaryTree binaryTree,int[] list){
        for (int i = 0; i < list.length; i++) {
            binaryTree.insertTreeNode(list[i]);
        }
        return binaryTree;
    }

    /**查找后续节点**/
    /**测试代码**/
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        /** 添加测试数据**/
        /**随机数**/
        Random random = new Random();
        int[] list = {10, 25, 13, 1, 6, 11, 15};
        binaryTree=binaryTree.insertTreeNodeByInt(binaryTree,list);

        findMaxNode(binaryTree.getRoot());
        findMinNode(binaryTree.getRoot());
        findPreNode(binaryTree.getRoot(), 16);
		System.out.println("root=" + binaryTree.getRoot().getValue());
        System.out.println(binaryTree.getRoot().leftTreeNode.getValue());
        System.out.println(binaryTree.getRoot().rightTreeNode.getValue());

        System.out.println("中序遍历--begin");
        binaryTree.inOrder(binaryTree.getRoot());
        System.out.println();
        System.out.println("中序遍历--end");

/**		System.out.println("前序遍历--begin");**/
/**		binaryTree.preOrder(binaryTree.getRoot());**/
/**		System.out.println("前序遍历--end");**/
/**
/**		System.out.println("后序遍历--begin");**/
/**		binaryTree.postOrder(binaryTree.getRoot());**/
/**		System.out.println("后序遍历--end");**/
/**
/**		System.out.println("root=" + binaryTree.getRoot().getValue());**/
/**		System.out.println("树的高度=" + binaryTree.height());**/
/**		System.out.println("树的节点数量=" + binaryTree.size());**/

        if (binaryTree.find(11) != null) {
            System.out.println("找到了");
        } else {
            System.out.println("没找到");
        }
        /** TreeNode dNode=new TreeNode(11);**/
        binaryTree.delete(11);

        /**删除测试 实际没有删除，只是将该节点的isDelete设为true**/
        if (binaryTree.find(11) != null) {
            System.out.println("找到了");
        } else {
            System.out.println("没找到");
        }
    }

}
